home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 8238 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  3.3 KB
  1. Path: camelot.dsccc.com!not-for-mail
  2. From: kcline@sun132.spd.dsccc.com (Kevin Cline)
  3. Newsgroups: comp.lang.pascal.misc,comp.lang.c++,comp.lang.c,comp.lang.pascal.borland
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Date: 15 Feb 1996 17:45:35 -0600
  6. Organization: DSC Communications Corporation Switch Products Division
  7. Message-ID: <4g0giv$94s@sun132.spd.dsccc.com>
  8. References: <4fr8be$ass@news.iconn.net>
  9. NNTP-Posting-Host: sun132.spd.dsccc.com
  10.  
  11. In article <4fr8be$ass@news.iconn.net>, The Crow <thecrow@iconn.net> wrote:
  12. >Here is what I am trying to do, I want to find the last NON-ZERO digit of a
  13. >given factorial.  For instance,
  14. >
  15. >5! = 120
  16. >
  17. >so the last non-zero digit is 2.  I want to be able to do this up to 1000.
  18. >Problem is, no matter how huge of a data-type you use, there isn't any way for
  19. >the computer to handle 1000!, it is however possible to find the last non-zero
  20. >digit somehow.  One thing I have tried is as I went through mulitplying the
  21. >series of numbers in the factorial (5 * 4 * 3 * 2) I would remove all the
  22. >trailing ZEROS, I got this to work up to 789, but it wont work with 1000 and i
  23. >am not really sure why.  If anyone has a clue how I can do this let me know.
  24. >
  25. >--
  26.  
  27. Since so many people have produced an incorrect solution to this problem,
  28. I thought it would be worthwhile posting the correct solution.
  29.  
  30. Everyone had the right idea, which is to keep only the last digit
  31. and compute the change when multiplying by the next number
  32. in the factorial, but couldn't figure out what to do
  33. about the numbers that end in 5, since that introduces a new zero
  34. in the series.  The answer is simple; when multiplying by five,
  35. take half of the previous digit +-5 to make an even number.
  36.  
  37. This works because 5 always follows 4, 4 x 5 = 20 (2),
  38. and 2 is half of 4.
  39.  
  40. You can make a multiplication table:
  41.  
  42.     old  1  2  3  4  5  6  7  8  9
  43. new
  44. 1        1  2  -  4  -  6  -  8  -
  45. 2        2  4  -  8  -  2  -  6  -
  46. 3        -  6  -  2  -  8  -  6  -
  47. 4        -  8  -  6  -  4  -  2  - 
  48. 5        -  4  -  8  -  2  -  6  - 
  49. 6        -  2  -  4  -  6  -  8  -
  50. 7        -  4  -  8  -  2  -  6  -
  51. 8        -  6  -  2  -  8  -  6  -
  52. 9        -  8  -  6  -  4  -  2  - 
  53.  
  54. The only factorials whose last non-zero digit is odd are 0! and 1!
  55.  
  56.     static int table[9][9] =
  57.     {{1, 2, 0, 4, 0, 6, 0, 8, 0 },
  58.      {2, 4, 0, 8, 0, 2, 0, 6, 0 },
  59.      {0, 6, 0, 2, 0, 8, 0, 6, 0 },
  60.      {0, 8, 0, 6, 0, 4, 0, 2, 0 }, 
  61.      {0, 4, 0, 8, 0, 2, 0, 6, 0 }, 
  62.      {0, 2, 0, 4, 0, 6, 0, 8, 0 },
  63.      {0, 4, 0, 8, 0, 2, 0, 6, 0 },
  64.      {0, 6, 0, 2, 0, 8, 0, 6, 0 },
  65.      {0, 8, 0, 6, 0, 4, 0, 2, 0 }}; 
  66.  
  67.     int last_non_zero_digit_of_factorial(n) {
  68.       digit = 1;
  69.       for (int i = 2; i < n ; ++i) {
  70.     while (i % 10 == 0) i /= 10;
  71.     digit = table[digit-1][i-1];
  72.       }
  73.       return digit;
  74.     }
  75.  
  76. This solution runs in O(n).  With a bit more thought a log(n) solution
  77. is possible.  Each cycle from 1-9 multiplies the last digit
  78. of the factorial by 8, so the last digit in 30! is equal to the 
  79. last digit of
  80.   8 [for 1-9] x 8 [for 11-19] x 8 [for 21-29] x 2 [20] x 3 [30] = 2.
  81.  
  82. The last digit of 427! is equal to the last digit of
  83.   8**41 [1-9,11-19,...,411-419] x 8**4 [10-90,110-190,210-290,310-390]
  84.    x 1 [410] x 2 [420] x 1 [100] x 2 [200] x 3 [300] x 4 [400]       
  85.  
  86.   = 8 x 6 x 2 x 2 x 3 x 4 (mod 10)
  87.   = 4 (mod 10)
  88.  
  89. The code is left as an exercise for the reader.
  90. -- 
  91. Kevin Cline
  92.